Degree Sequence
   HOME

TheInfoList



OR:

In
graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
, the degree (or valency) of a
vertex Vertex, vertices or vertexes may refer to: Science and technology Mathematics and computer science *Vertex (geometry), a point where two or more curves, lines, or edges meet *Vertex (computer graphics), a data structure that describes the position ...
of a
graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...
is the number of
edges Edge or EDGE may refer to: Technology Computing * Edge computing, a network load-balancing system * Edge device, an entry point to a computer network * Adobe Edge, a graphical development application * Microsoft Edge, a web browser developed by ...
that are
incident Incident may refer to: * A property of a graph in graph theory * ''Incident'' (film), a 1948 film noir * Incident (festival), a cultural festival of The National Institute of Technology in Surathkal, Karnataka, India * Incident (Scientology), a ...
to the vertex; in a
multigraph In mathematics, and more specifically in graph theory, a multigraph is a graph which is permitted to have multiple edges (also called ''parallel edges''), that is, edges that have the same end nodes. Thus two vertices may be connected by more ...
, a
loop Loop or LOOP may refer to: Brands and enterprises * Loop (mobile), a Bulgarian virtual network operator and co-founder of Loop Live * Loop, clothing, a company founded by Carlos Vasquez in the 1990s and worn by Digable Planets * Loop Mobile, an ...
contributes 2 to a vertex's degree, for the two ends of the edge. The degree of a vertex v is denoted \deg(v) or \deg v. The maximum degree of a graph G, denoted by \Delta(G), and the minimum degree of a graph, denoted by \delta(G), are the maximum and minimum of its vertices' degrees. In the multigraph shown on the right, the maximum degree is 5 and the minimum degree is 0. In a
regular graph In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree o ...
, every vertex has the same degree, and so we can speak of ''the'' degree of the graph. A
complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is c ...
(denoted K_n, where n is the number of vertices in the graph) is a special kind of regular graph where all vertices have the maximum possible degree, n-1. In a
signed graph In the area of graph theory in mathematics, a signed graph is a graph in which each edge has a positive or negative sign. A signed graph is balanced if the product of edge signs around every cycle is positive. The name "signed graph" and the no ...
, the number of positive edges connected to the vertex v is called positive deg(v) and the number of connected negative edges is entitled negative deg(v).


Handshaking lemma

The degree sum formula states that, given a graph G=(V, E), :\sum_ \deg(v) = 2, E, \, . The formula implies that in any undirected graph, the number of vertices with odd degree is even. This statement (as well as the degree sum formula) is known as the
handshaking lemma In graph theory, a branch of mathematics, the handshaking lemma is the statement that, in every finite undirected graph, the number of vertices that touch an odd number of edges is even. In more colloquial terms, in a party of people some of whom ...
. The latter name comes from a popular mathematical problem, which is to prove that in any group of people, the number of people who have shaken hands with an odd number of other people from the group is even.


Degree sequence

The degree sequence of an undirected graph is the non-increasing sequence of its vertex degrees; for the above graph it is (5, 3, 3, 2, 2, 1, 0). The degree sequence is a
graph invariant Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties * Graph (topology), a topological space resembling a graph in the sense of discr ...
, so isomorphic graphs have the same degree sequence. However, the degree sequence does not, in general, uniquely identify a graph; in some cases, non-isomorphic graphs have the same degree sequence. The degree sequence problem is the problem of finding some or all graphs with the degree sequence being a given non-increasing sequence of positive integers. (Trailing zeroes may be ignored since they are trivially realized by adding an appropriate number of isolated vertices to the graph.) A sequence which is the degree sequence of some graph, i.e. for which the degree sequence problem has a solution, is called a graphic or graphical sequence. As a consequence of the degree sum formula, any sequence with an odd sum, such as (3, 3, 1), cannot be realized as the degree sequence of a graph. The inverse is also true: if a sequence has an even sum, it is the degree sequence of a multigraph. The construction of such a graph is straightforward: connect vertices with odd degrees in pairs (forming a matching), and fill out the remaining even degree counts by self-loops. The question of whether a given degree sequence can be realized by a
simple graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' ve ...
is more challenging. This problem is also called
graph realization problem The graph realization problem is a decision problem in graph theory. Given a finite sequence (d_1,\dots,d_n) of natural numbers, the problem asks whether there is a labeled simple graph such that (d_1,\dots,d_n) is the degree sequence of this grap ...
and can be solved by either the
Erdős–Gallai theorem The Erdős–Gallai theorem is a result in graph theory, a branch of combinatorial mathematics. It provides one of two known approaches to solving the graph realization problem, i.e. it gives a necessary and sufficient condition for a finite sequen ...
or the
Havel–Hakimi algorithm The Havel–Hakimi algorithm is an algorithm in graph theory solving the graph realization problem. That is, it answers the following question: ''Given a finite list of nonnegative integers in non-increasing order, is there a simple graph such th ...
. The problem of finding or estimating the number of graphs with a given degree sequence is a problem from the field of
graph enumeration In combinatorics, an area of mathematics, graph enumeration describes a class of combinatorial enumeration problems in which one must count undirected or directed graphs of certain types, typically as a function of the number of vertices of the gra ...
. More generally, the degree sequence of a
hypergraph In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices. Formally, an undirected hypergraph H is a pair H = (X,E) wh ...
is the non-increasing sequence of its vertex degrees. A sequence is k-graphic if it is the degree sequence of some k-uniform hypergraph. In particular, a 2-graphic sequence is graphic. Deciding if a given sequence is k-graphic is doable in
polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
for k=2 via the
Erdős–Gallai theorem The Erdős–Gallai theorem is a result in graph theory, a branch of combinatorial mathematics. It provides one of two known approaches to solving the graph realization problem, i.e. it gives a necessary and sufficient condition for a finite sequen ...
but is
NP-complete In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...
for all k\ge 3 (Deza et al., 2018 ).


Special values

*A vertex with degree 0 is called an
isolated vertex In discrete mathematics, and more specifically in graph theory, a vertex (plural vertices) or node is the fundamental unit of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges (unordered pairs of ve ...
. *A vertex with degree 1 is called a leaf vertex or end vertex or a pendant vertex, and the edge incident with that vertex is called a pendant edge. In the graph on the right, is a pendant edge. This terminology is common in the study of
tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...
s in graph theory and especially
tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...
s as
data structure In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, a ...
s. * A vertex with degree ''n'' − 1 in a graph on ''n'' vertices is called a
dominating vertex In graph theory, a universal vertex is a vertex of an undirected graph that is adjacent to all other vertices of the graph. It may also be called a dominating vertex, as it forms a one-element dominating set in the graph. (It is not to be confused ...
.


Global properties

*If each vertex of the graph has the same degree ''k'', the graph is called a ''k''-regular graph and the graph itself is said to have degree ''k''. Similarly, a
bipartite graph In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are ...
in which every two vertices on the same side of the bipartition as each other have the same degree is called a
biregular graph In graph-theoretic mathematics, a biregular graph or semiregular bipartite graph is a bipartite graph G=(U,V,E) for which every two vertices on the same side of the given bipartition have the same degree as each other. If the degree of the vertice ...
. *An undirected, connected graph has an
Eulerian path In graph theory, an Eulerian trail (or Eulerian path) is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices). Similarly, an Eulerian circuit or Eulerian cycle is an Eulerian trail that starts and ends ...
if and only if it has either 0 or 2 vertices of odd degree. If it has 0 vertices of odd degree, the Eulerian path is an Eulerian circuit. *A directed graph is a
directed pseudoforest In graph theory, a pseudoforest is an undirected graphThe kind of undirected graph considered here is often called a multigraph or pseudograph, to distinguish it from a simple graph. in which every connected component has at most one cycle. Tha ...
if and only if every vertex has outdegree at most 1. A
functional graph In graph theory, a pseudoforest is an undirected graphThe kind of undirected graph considered here is often called a multigraph or pseudograph, to distinguish it from a simple graph. in which every connected component has at most one cycle. That ...
is a special case of a pseudoforest in which every vertex has outdegree exactly 1. *By
Brooks' theorem In graph theory, Brooks' theorem states a relationship between the maximum degree of a graph and its chromatic number. According to the theorem, in a connected graph in which every vertex has at most Δ neighbors, the vertices can be colored with o ...
, any graph ''G'' other than a clique or an odd cycle has
chromatic number In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...
at most Δ(''G''), and by
Vizing's theorem In graph theory, Vizing's theorem states that every simple undirected graph may be edge colored using a number of colors that is at most one larger than the maximum degree of the graph. At least colors are always necessary, so the undirected grap ...
any graph has
chromatic index In graph theory, an edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue ...
at most Δ(''G'') + 1. *A ''k''-degenerate graph is a graph in which each subgraph has a vertex of degree at most ''k''.


See also

*
Indegree In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. Definition In formal terms, a directed graph is an ordered pa ...
,
outdegree In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. Definition In formal terms, a directed graph is an ordered pai ...
for digraphs *
Degree distribution In the study of graphs and networks, the degree of a node in a network is the number of connections it has to other nodes and the degree distribution is the probability distribution of these degrees over the whole network. Definition The degree o ...
* Degree sequence for bipartite graphs


Notes


References

*. *. * *. *{{citation , last1 = Sierksma , first1 = Gerard , last2 = Hoogeveen , first2 = Han , doi = 10.1002/jgt.3190150209 , issue = 2 , journal =
Journal of Graph Theory The ''Journal of Graph Theory'' is a peer-reviewed mathematics journal specializing in graph theory and related areas, such as structural results about graphs, graph algorithms with theoretical emphasis, and discrete optimization on graphs. The s ...
, mr = 1106533 , pages = 223–231 , title = Seven criteria for integer sequences being graphic , volume = 15 , year = 1991, url = https://ir.cwi.nl/pub/1579 . Graph theory